/*
	Name:algorithm-dp
	Copyright:Easonlee
	Author:Easonlee
	Date:
	Description:
*/
#ifndef _DP_
#define _DP_ 1

#pragma GCC system_header

#include "algorithm_config.h"
#include "STL/myvector.h"

namespace algorithm{
	class bag{
		private:
			algorithm::myvector<algorithm::myvector<int> > bag;
		public:
			void init_bag_from_nw(int n,int w){
				bag.init();
				algorithm::myvector<int> cache;
				cache.init_size(w);
				for(int i=0;i<n;i++){
					bag.push_back(cache);
				}
			}
			void make_bag_from_vw(/*algorithm::myvector<int> v,*/algorithm::myvector<int> w){
				for(int i=0;i<bag.sizex();i++){
					for(int j=0;j<w.lengthx();j++){
						if(i==0){
							bag[i].set_number(j,1);
						}
						else{
							if(j==w[i]){
								bag[i].set_number(j,1);
							}
							if(bag[i-1][j-w[i]]==1){
								bag[i].set_number(j,1);
							}
							if(bag[i-1][j]==1){
								bag[i].set_number(j,1);
							}
						}
					}
				}
			}
			int bagnumber(int i,int j){
				return bag[i-1][j-1];
			}
			int maxbag(){
				return this->bagnumber(bag.sizex(),bag[1].sizex());
			}
	};
}

#endif
